{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Value of K Coins From Piles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxValueOfCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从栈中取出 K 个硬币的最大面值和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一张桌子上总共有 <code>n</code>&nbsp;个硬币 <b>栈</b>&nbsp;。每个栈有 <strong>正整数</strong>&nbsp;个带面值的硬币。</p>\n",
    "\n",
    "<p>每一次操作中，你可以从任意一个栈的 <strong>顶部</strong>&nbsp;取出 1 个硬币，从栈中移除它，并放入你的钱包里。</p>\n",
    "\n",
    "<p>给你一个列表&nbsp;<code>piles</code>&nbsp;，其中&nbsp;<code>piles[i]</code>&nbsp;是一个整数数组，分别表示第 <code>i</code>&nbsp;个栈里 <strong>从顶到底</strong>&nbsp;的硬币面值。同时给你一个正整数&nbsp;<code>k</code>&nbsp;，请你返回在&nbsp;<strong>恰好</strong>&nbsp;进行&nbsp;<code>k</code>&nbsp;次操作的前提下，你钱包里硬币面值之和&nbsp;<strong>最大为多少</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/09/e1.png\" style=\"width: 600px; height: 243px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>piles = [[1,100,3],[7,8,9]], k = 2\n",
    "<b>输出：</b>101\n",
    "<strong>解释：</strong>\n",
    "上图展示了几种选择 k 个硬币的不同方法。\n",
    "我们可以得到的最大面值为 101 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7\n",
    "<b>输出：</b>706\n",
    "<strong>解释：\n",
    "</strong>如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == piles.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= piles[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= sum(piles[i].length) &lt;= 2000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-value-of-k-coins-from-piles](https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-value-of-k-coins-from-piles](https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,100,3],[7,8,9]]\\n2', '[[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        f = [0] * (k + 1)\n",
    "        sum_n = 0\n",
    "        for pile in piles:\n",
    "            n = len(pile)\n",
    "            for i in range(1, n):\n",
    "                pile[i] += pile[i - 1]  # pile 前缀和\n",
    "            sum_n = min(sum_n + n, k)  # 优化：j 从前 i 个栈的大小之和开始枚举（不超过 k）\n",
    "            for j in range(sum_n, 0, -1):\n",
    "                f[j] = max(f[j], max(f[j - w - 1] + pile[w] for w in range(min(n, j))))  # w 从 0 开始，物品体积为 w+1\n",
    "        return f[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n=len(piles)\n",
    "        pre=[[0]*(k+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            tmp=piles[i][0]\n",
    "            pre[i][1]=tmp\n",
    "            for j in range(1,min(k,len(piles[i]))):\n",
    "                pre[i][j+1]=tmp+piles[i][j]\n",
    "                tmp=pre[i][j+1]\n",
    "        # pre=[]\n",
    "        # for pile in piles:\n",
    "        #     ts=[0]\n",
    "        #     for p in pile:\n",
    "        #         ts.append(ts[-1]+p)\n",
    "        #     pre.append(ts)\n",
    "\n",
    "        dp0=[0]*(k+1) \n",
    "        for i in range(n):\n",
    "            dp=[0]*(k+1)\n",
    "            for j in range(k+1):\n",
    "                dp[j]=max(dp0[j-x]+pre[i][x] for x in range(min(j+1,k+1,len(piles[i])+1)))\n",
    "            dp0=dp\n",
    "        # dp=[0]*(k+1)\n",
    "        # for sp in pre:\n",
    "        #     dp0=[0]*(k+1)\n",
    "        #     for y in range(k+1):\n",
    "        #         for x in range(min(y+1,len(sp),k+1)):\n",
    "        #             dp0[y]=max(dp0[y],dp[y-x]+sp[x])\n",
    "        #     dp=dp0\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        \n",
    "        @lru_cache(10000)\n",
    "        def help(a, b):\n",
    "            if b == 0:\n",
    "                return 0\n",
    "            if a == n-1:\n",
    "                m = len(piles[a])\n",
    "                return sum(piles[a][:min(m, b)])\n",
    "            \n",
    "            m = len(piles[a])\n",
    "            p = []\n",
    "            for i in range(min(m, b)+1):\n",
    "                p.append(sum(piles[a][:i])+help(a+1, b-i))\n",
    "            return max(p)\n",
    "        return help(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            tt = 0\n",
    "            for j in range(len(piles[i])):\n",
    "                tt += piles[i][j]\n",
    "                for q in range(min(s + 1, k - j)):\n",
    "                    dp[i + 1][j + 1 + q] = max(dp[i + 1][j + 1 + q], dp[i][j + 1 + q], dp[i][q] + tt)\n",
    "            s += len(piles[i])\n",
    "            # for j in range(k + 1): dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        dp = np.zeros(k+1)\n",
    "        for pile in piles:\n",
    "            temp = dp.copy()\n",
    "            for used, value in enumerate(accumulate(pile), 1):\n",
    "                if used > k: break\n",
    "                dp = np.maximum(dp, np.concatenate((np.zeros(used), temp[:-used] + value)))\n",
    "        return int(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        self.piles = piles\n",
    "        n = len(piles)\n",
    "        return self.func1(0, n, k)\n",
    "    \n",
    "    @cache\n",
    "    def func1(self, left, right, k):\n",
    "        subp = self.piles[left:right]\n",
    "        n = len(subp)\n",
    "        maxv = 0\n",
    "        lp = 0\n",
    "        for pile in subp:\n",
    "            lp += len(pile)\n",
    "        if lp < k:\n",
    "            return -1\n",
    "        if lp == k:\n",
    "            return sum(sum(pile) for pile in subp)\n",
    "        if n == 1:\n",
    "            return sum(subp[0][:k])\n",
    "        for k0 in range(k + 1):\n",
    "            maxv = max(maxv, self.func1(left, left + (right - left) // 2, k0) + self.func1(left + (right - left) // 2, right, k - k0))\n",
    "        return maxv\n",
    "\n",
    "# 示例用法\n",
    "if __name__ == '__main__':\n",
    "    piles = [[2, 4, 5], [1, 2, 3], [10, 20]]\n",
    "    k = 5\n",
    "    solution = Solution()\n",
    "    result = solution.maxValueOfCoins(piles, k)\n",
    "    print(result)  # 输出最大价值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: list[list[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        tot = 0\n",
    "        # 栈数\n",
    "        for i in range(1, n + 1):\n",
    "            tot += len(piles[i - 1])\n",
    "            # 总的硬币数\n",
    "            for j in range(1, min(k, tot) + 1):\n",
    "                sum_ = 0\n",
    "                # 最后一个栈的硬币数\n",
    "                for t in range(0, min(j, len(piles[i - 1])) + 1):\n",
    "                    if t:\n",
    "                        sum_ += piles[i - 1][t - 1]\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - t] + sum_)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "\n",
    "        n = len(piles)\n",
    "        dp = [[0]*(n+1) for _ in range(k+1)]\n",
    "\n",
    "        weight = [collections.defaultdict(int) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            sums = 0 \n",
    "            for j in range(len(piles[i])):\n",
    "                sums += piles[i][j]\n",
    "                weight[i][j] = sums \n",
    "\n",
    "        #print(weight)\n",
    "        for i in range(1,k+1):\n",
    "            for j in range(1,n+1):\n",
    "                for y in range(1, min(i+1,len(piles[j-1])+1   )):\n",
    "                    if dp[i-y][j-1]+weight[j-1][y-1]>dp[i][j]:\n",
    "                        dp[i][j] = dp[i-y][j-1]+weight[j-1][y-1]\n",
    "                    if dp[i][j-1]>dp[i][j]:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "    \n",
    "        return dp[k][n]\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        self.piles=piles\n",
    "        return self.func1(0,len(piles),k)\n",
    "    @cache\n",
    "    def func1(self,start,end,k):\n",
    "        if k==0:\n",
    "            return 0\n",
    "        if k>reduce(lambda a,b:a+len(b),self.piles[start:end],0):\n",
    "            return -1\n",
    "        n=end-start\n",
    "        if n==1:\n",
    "            return sum(self.piles[start][:k])\n",
    "        n1=n//2\n",
    "        res=0\n",
    "        for i in range(k+1):\n",
    "            res=max(res,self.func1(start,start+n1,i)+self.func1(start+n1,end,k-i))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n=len(piles)\n",
    "        dp=[[0 for _ in range(k+1)]for _ in range(n)]\n",
    "        pre=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            tp=0\n",
    "            for j in range(min(k,len(piles[i]))):\n",
    "                tp+=piles[i][j]\n",
    "                pre[i].append((tp,j+1))\n",
    "        #print(pre)\n",
    "        ans=0\n",
    "        for cost,use in pre[0]:\n",
    "            dp[0][use]=cost\n",
    "            ans=max(ans,cost)\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,k+1):\n",
    "                dp[i][j]=dp[i-1][j]\n",
    "                for cost,use in pre[i]:\n",
    "                    if use<=j:\n",
    "                        dp[i][j]=max(dp[i][j],dp[i-1][j-use]+cost)\n",
    "                        if dp[i][j]>ans:\n",
    "                            ans=dp[i][j]\n",
    "        #print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        for i in piles:\n",
    "            for j, element in enumerate(i):\n",
    "                if j-1 >=0:\n",
    "                    i[j] += i[j-1]\n",
    "        print(piles)\n",
    "        row, col = len(piles), len(piles[0])\n",
    "        dp = [[0 for _ in range(k+1)] for _ in range(row+1)]\n",
    "        for i in range(1, row+1):\n",
    "            for j in range(k+1):\n",
    "                for x, element in enumerate(piles[i-1]):\n",
    "                    weight = x+1\n",
    "                    value = element \n",
    "                    if j >= weight:\n",
    "                        dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i-1][j - weight] + value) \n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i][j], dp[i-1][j])\n",
    "        print(dp)\n",
    "        return dp[row][k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        # dp[i][j] = max(dp[i-1][0] + h[j],dp[i-1][1],h[j-1]....)\n",
    "        n = len(piles)\n",
    "        dp = [[0]*(k+1) for _ in range(n)]\n",
    "        for j in range(1,k+1):\n",
    "            if len(piles[0])>=j:\n",
    "                dp[0][j]=dp[0][j-1] + piles[0][j-1]\n",
    "            else:\n",
    "                break\n",
    "        t = [[0]*(k+1) for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,k+1):\n",
    "                if len(piles[i])>=j:\n",
    "                    t[i][j] = t[i][j-1] + piles[i][j-1]\n",
    "                else:\n",
    "                    break\n",
    "        #print(dp,t)\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,k+1):\n",
    "                a = min(len(piles[i])+1,j+1)\n",
    "                for l in range(a):\n",
    "                    dp[i][j] = max(dp[i][j],dp[i-1][j-l]+t[i][l])\n",
    "                    #print(i,j,dp[i][j])\n",
    "        #print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(idx: int, cnt: int) -> int:\n",
    "            result = 0\n",
    "            if cnt == 0:\n",
    "                return 0\n",
    "            if idx >= len(piles):\n",
    "                return 0\n",
    "\n",
    "            if cnt >= rest[idx]:\n",
    "                if idx + 1 < len(piles):\n",
    "                    return sum(piles[idx]) + dfs(idx + 1, rest[idx + 1])\n",
    "                return sum(piles[idx])\n",
    "\n",
    "            result = dfs(idx + 1, cnt)\n",
    "            base = 0\n",
    "            for i in range(min(len(piles[idx]), cnt)):\n",
    "                base += piles[idx][i]\n",
    "                result = max(result, base + dfs(idx + 1, cnt - i -1))\n",
    "            return result\n",
    "\n",
    "        piles.sort(key = lambda x: -len(x))\n",
    "        rest = [len(piles[-1])] * len(piles)\n",
    "        for i in range(len(rest) -2, -1, -1):\n",
    "            rest[i] = rest[i + 1] + len(piles[i])\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        result=[]\n",
    "        prefix=[]\n",
    "        n=len(piles)\n",
    "        for i in range(n):\n",
    "            prefix.append([])\n",
    "            result.append([])\n",
    "        for i in range(n):\n",
    "            for j in range(k+1):\n",
    "                result[i].append(0)\n",
    "                if j<=len(piles[i]):\n",
    "                    prefix[i].append(sum(piles[i][:j]))\n",
    "                else:\n",
    "                    prefix[i].append(0)\n",
    "        # print(prefix[0][0])\n",
    "        # print(prefix[0][1])\n",
    "        # print(prefix[0][2])\n",
    "        length=[len(piles[0])]*n\n",
    "        for i in range(1,n):\n",
    "            length[i]=length[i-1]+len(piles[i])\n",
    "\n",
    "        # print(\"prefix[0]=\",prefix[0])\n",
    "        result[0]=prefix[0]\n",
    "        for i in range(1,n):\n",
    "            # print(\"i=\",i)\n",
    "            # print(\"prefix[\",i,\"]=\",prefix[i])\n",
    "            for j in range(0,k+1):\n",
    "                # if j>sum(len(piles[t]) for t in range(i+1)):\n",
    "                if j>length[i]:\n",
    "                    break\n",
    "                # print(\"j=\",j)\n",
    "                # for num in range(0,min(j+1,1+sum(len(piles[t]) for t in range(i)))):\n",
    "                for num in range(0,j+1):\n",
    "                    if num>len(piles[i]):\n",
    "                        break\n",
    "                    if result[i][j]<result[i-1][j-num]+prefix[i][num]:\n",
    "                        result[i][j]=result[i-1][j-num]+prefix[i][num]\n",
    "                    # # if num>(sum(len(piles[t]) for t in range(i))):\n",
    "                    # if num>length[i-1]:\n",
    "                    #     break\n",
    "                    # # print(\"i=\",i,\"---j=\",j,\"---num=\",num)\n",
    "                    # if result[i][j]<result[i-1][num]+prefix[i][j-num]:\n",
    "                    #     result[i][j]=result[i-1][num]+prefix[i][j-num]\n",
    "                # print(\"result[\",i,\"]=\",result[i])\n",
    "\n",
    "        return result[n-1][k]\n",
    "\n",
    "# class Solution:\n",
    "#     def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "#         # dp[num]表示取num个硬币的时候最多能拿到多少钱\n",
    "#         dp = [0] * (k + 1)\n",
    "\n",
    "#         for i, pile in enumerate(piles):\n",
    "#             # 初始化滚动的dp数组\n",
    "#             temp_dp = [0] * (k + 1)\n",
    "\n",
    "#             # 不需要求整个前缀和数组，因为最多只能取k枚硬币，那么在piles[i]里最多也只能取k枚，\n",
    "#             # 因而只需要计算前min(len(pile), k)个数的前缀和即可。\n",
    "#             m = min(len(pile), k)\n",
    "#             pre_sum = [0] * (m + 1)\n",
    "#             for j in range(m):\n",
    "#                 pre_sum[j + 1] = pre_sum[j] + pile[j]\n",
    "\n",
    "#             # 在外循环中对在piles[i]中取硬币的数量进行遍历，因为m有可能小于k，这样可以在不合法时提前结束\n",
    "#             for p in range(m + 1):\n",
    "#                 # 内循环中对dp[i-1]中记录的选取数量进行遍历\n",
    "#                 for q in range(k + 1):\n",
    "#                     # p+q是当前遍历到的选取总数，那么显然这个数量不能超过k，否则直接break\n",
    "#                     num = p + q\n",
    "#                     if num > k:\n",
    "#                         break\n",
    "#                     # 而当 dp[q] == 0 且 q != 0 时说明在前i个（截至下标i-1）piles中，\n",
    "#                     # 根本无法取到q枚及以上硬币，可以break\n",
    "#                     if dp[q] == 0 and q != 0:\n",
    "#                         break\n",
    "#                     if pre_sum[p] + dp[q] > temp_dp[num]:\n",
    "#                         temp_dp[num] = pre_sum[p] + dp[q]\n",
    "#             dp = temp_dp\n",
    "\n",
    "#         return dp[-1]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "\n",
    "#         # 前缀和\n",
    "#         pre = []\n",
    "#         for pile in piles:\n",
    "#             acc = [0]\n",
    "#             for dp in pile:\n",
    "#                 acc.append(acc[-1] + dp)\n",
    "#             pre.append(acc)\n",
    "\n",
    "#         # 初始化\n",
    "#         dp = defaultdict(lambda:defaultdict(int))\n",
    "#         for x in range(min(k, len(piles[0])) + 1):  # 不能超过堆的长度\n",
    "#             dp[0][x] = pre[0][x]\n",
    "\n",
    "#         # 递推\n",
    "#         for curIdx in range(1, len(piles)):\n",
    "#             for y in range(k + 1):\n",
    "#                 for x in range(min(y, len(piles[curIdx])) + 1):  # 不能超过堆的长度\n",
    "#                     dp[curIdx][y] = max(\n",
    "#                         dp[curIdx][y],\n",
    "#                         dp[curIdx - 1][y - x] + pre[curIdx][x])\n",
    "\n",
    "#         return dp[len(piles) - 1][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        pre = [list(itertools.accumulate(p, initial=0)) for p in piles]\n",
    "        l = [len(p) for p in piles]\n",
    "        pl = list(itertools.accumulate(l, initial=0))\n",
    "        @cache\n",
    "        def f(i, x):\n",
    "            if x > pl[i+1]:\n",
    "                return -math.inf\n",
    "            if i == 0:\n",
    "                return pre[0][x]\n",
    "            ans = -math.inf\n",
    "            for j in range(min(x,l[i])+1):\n",
    "                ans = max(ans, f(i-1, x-j) + pre[i][j])\n",
    "            return ans\n",
    "\n",
    "        return f(n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        # Solution: Dynamic Programming\n",
    "        n = len(piles)\n",
    "\n",
    "        # Step 1: Construct the state-transition matrix\n",
    "        dp = [[0] * (k + 1) for _ in range(n)]\n",
    "\n",
    "        # Step 2: Set the initial state\n",
    "        dp[-1][0] = 0\n",
    "        for i in range(1, k + 1):\n",
    "            dp[-1][i] = sum(piles[-1][:i])\n",
    "\n",
    "        # Step 3: Define the state-transition relationship\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(k + 1):\n",
    "                _sum = 0\n",
    "                for m in range(min(j, len(piles[i])) + 1):\n",
    "                    dp[i][j] = max(dp[i][j], _sum + dp[i + 1][j - m])\n",
    "                    if m < len(piles[i]):\n",
    "                        _sum += piles[i][m]\n",
    "        \n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        sums = [0]\n",
    "        nums = []\n",
    "        for i in range(n):\n",
    "            nums.extend(piles[i])\n",
    "            sums.append(sums[-1] + len(piles[i]))\n",
    "        table = [[-1] * (k + 1) for _ in range(len(nums) + 1)]\n",
    "        return self.search(piles, nums, sums, 0, k, table)\n",
    "        \n",
    "    def search(self, piles, nums, sums, i, k, table):\n",
    "        if table[i][k] == -1:\n",
    "            n = len(nums)\n",
    "            m = len(sums)\n",
    "            if i == n:\n",
    "                if k == 0:\n",
    "                    table[i][k] = 0\n",
    "                else:\n",
    "                    table[i][k] = float('-inf')\n",
    "            else:\n",
    "                if k == 0:\n",
    "                    table[i][k] = 0\n",
    "                else:\n",
    "                    x = self.search(piles, nums, sums, i + 1, k - 1, table) + nums[i]\n",
    "                    j = bisect.bisect_right(sums, i)\n",
    "                    if j < m:\n",
    "                        t = sums[j]\n",
    "                    else:\n",
    "                        t = n\n",
    "                    y = self.search(piles, nums, sums, t, k, table)\n",
    "                    table[i][k] = max(x, y)\n",
    "        return table[i][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        # 计算前缀和\n",
    "        pre = []\n",
    "        for pile in piles:\n",
    "            # 对于每个栈，计算前缀和\n",
    "            pre_p = [0]\n",
    "            for pi in pile:\n",
    "                pre_p.append(pre_p[-1]+pi)\n",
    "            pre.append(pre_p[1:])\n",
    "        # print(pre)\n",
    "        # 多重背包\n",
    "        # dp初始化\n",
    "        dp = defaultdict(lambda:defaultdict(int))\n",
    "        for i in range(1,len(piles)+1): # 截至到第i个栈\n",
    "            for kk in range(1,k+1): #消耗的硬币数量\n",
    "                for v in range(0,len(piles[i-1])): # 第i个栈取多少个硬币\n",
    "                    if kk >= v + 1: # 如果，当前还能放得进硬币\n",
    "                        # print(i,kk,v+1,dp[i][kk],dp[i-1][kk - v - 1],pre[i-1][v])\n",
    "                        dp[i][kk] = max(dp[i][kk], dp[i-1][kk], dp[i-1][kk - v - 1] + pre[i-1][v])\n",
    "                        # print(\"set\",i,kk,dp[i][kk])\n",
    "        return dp[len(piles)][k]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "\n",
    "        # 前缀和\n",
    "        pre = []\n",
    "        for pile in piles:\n",
    "            acc = [0]\n",
    "            for dp in pile:\n",
    "                acc.append(acc[-1] + dp)\n",
    "            pre.append(acc)\n",
    "\n",
    "        # 初始化\n",
    "        dp = defaultdict(lambda:defaultdict(int))\n",
    "        for x in range(min(k, len(piles[0])) + 1):  # 不能超过堆的长度\n",
    "            dp[0][x] = pre[0][x]\n",
    "\n",
    "        # 递推\n",
    "        for curIdx in range(1, len(piles)):\n",
    "            for y in range(k + 1):\n",
    "                for x in range(min(y, len(piles[curIdx])) + 1):  # 不能超过堆的长度\n",
    "                    dp[curIdx][y] = max(\n",
    "                        dp[curIdx][y],\n",
    "                        dp[curIdx - 1][y - x] + pre[curIdx][x])\n",
    "\n",
    "        return dp[len(piles) - 1][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        valueList = []\n",
    "        weightList = []\n",
    "        n = len(piles)\n",
    "        for i in range(n):\n",
    "            for j in range(len(piles[i])):\n",
    "                valueList.append(sum(piles[i][0:j + 1]))\n",
    "                weightList.append(j + 1)\n",
    "        n = len(valueList)\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = max(dp[i - 1][j], (dp[i - weightList[i - 1]][j - weightList[i - 1]] + valueList[i - 1] if j >= weightList[i - 1] else 0))\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Item:\n",
    "    def __init__(self, value, weight):\n",
    "        self.value = value\n",
    "        self.weight = weight\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles, k: int) -> int:\n",
    "        items = []\n",
    "        for pile in piles:\n",
    "            _items = []\n",
    "            i = 1\n",
    "            for value in accumulate(pile):\n",
    "                _items.append(Item(value, i))\n",
    "                i += 1\n",
    "            items.append(_items)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, w):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "            for item in items[i]:\n",
    "                if w - item.weight >= 0:\n",
    "                    ans = max(ans, item.value + dfs(i-1, w - item.weight))\n",
    "\n",
    "            ans = max(ans, dfs(i-1, w))\n",
    "            return ans\n",
    "\n",
    "        return dfs(len(items)-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        for i,row in enumerate(piles):\n",
    "            for j in range(1,len(row)):\n",
    "                row[j]+= row[j-1]\n",
    "            row.insert(0,0)\n",
    "        piles.sort(key = len,reverse = True)\n",
    "        @lru_cache(None)\n",
    "        def dp(i,k):\n",
    "            if i==0 or k==0:\n",
    "                return 0\n",
    "            row = piles[i-1]\n",
    "            return max(dp(i-1,k-j)+row[j] for j in range(0, min(len(row), k+1)))\n",
    "        return dp(len(piles), k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        memo={}\n",
    "        def maxpick(i, k,memo):\n",
    "            if (i,k ) in memo:\n",
    "                return memo[(i,k)]\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if i >= len(piles):\n",
    "                return float(\"-inf\")\n",
    "            s = 0\n",
    "            j = 0\n",
    "            res = maxpick(i + 1, k,memo)\n",
    "\n",
    "            while j <k and j <len(piles[i]):\n",
    "                s+=piles[i][j]\n",
    "                j+=1\n",
    "                res = max(res,s + maxpick(i + 1, k-j,memo))\n",
    "            memo[(i,k)]=res\n",
    "            return res\n",
    "        return maxpick(0, k,memo)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \n",
    "        def dp(i, k, left):\n",
    "            if (i,k) in cache:\n",
    "                return cache[(i,k)]\n",
    "                \n",
    "            if k == 0:\n",
    "                res = 0\n",
    "            elif i == len(piles) or left < k:\n",
    "                res = -math.inf\n",
    "            elif left == k:\n",
    "                take = len(piles[i])\n",
    "                res = sum(piles[i])+dp(i+1,k-take,left-take)\n",
    "            else:\n",
    "                take = min(len(piles[i]),k)\n",
    "                base = 0\n",
    "                res = dp(i+1,k,left)\n",
    "                for t in range(1, take+1):\n",
    "                    base += piles[i][t-1]\n",
    "                    res = max(res, base+dp(i+1,k-t,left-t))\n",
    "            \n",
    "            cache[(i,k)] = res\n",
    "            return res\n",
    "\n",
    "        cache = {}\n",
    "        return dp(0,k,sum(len(pile) for pile in piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        l = len(piles)\n",
    "        @cache\n",
    "        def dfs(i, k):#i为第i个栈，k为取出数量\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if i == l:\n",
    "                return float(\"-inf\")\n",
    "            s = 0\n",
    "            res = dfs(i + 1, k)#如果此栈不取出的值\n",
    "            for j in range(min(len(piles[i]), k + 1)):\n",
    "                s += piles[i][j]\n",
    "                k -= 1\n",
    "                res = max(res, s + dfs(i + 1, k))#此栈中取出j + 1个值的最大值\n",
    "            return res\n",
    "        return dfs(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        # choose coin on top \n",
    "        @cache\n",
    "        def dfs(i: int, remain: int):\n",
    "            if remain == 0:\n",
    "                return 0\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            res = s = 0\n",
    "            # 最多选remain个, 或者0个\n",
    "            for j in range(min(remain, len(piles[i]))):\n",
    "                s += piles[i][j]\n",
    "                res = max(res, s + dfs(i + 1, remain - (j + 1)))\n",
    "            res = max(res, dfs(i + 1, remain))\n",
    "            print(res)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \n",
    "        def dp(i, k, left):\n",
    "            if (i,k) in cache:\n",
    "                return cache[(i,k)]\n",
    "                \n",
    "            if k == 0:\n",
    "                res = 0\n",
    "            elif i == len(piles) or left < k:\n",
    "                res = -math.inf\n",
    "            elif left == k:\n",
    "                take = len(piles[i])\n",
    "                res = presums[i][-1]+dp(i+1,k-take,left-take)\n",
    "            else:\n",
    "                take = min(len(piles[i]),k)\n",
    "                res =  max(presums[i][t]+dp(i+1,k-t,left-t)\n",
    "                            for t in range(take+1))\n",
    "            \n",
    "            cache[(i,k)] = res\n",
    "            return res\n",
    "\n",
    "        cache = {}\n",
    "        presums = []\n",
    "        total = 0\n",
    "        for pile in piles:\n",
    "            presums.append(list(itertools.accumulate(pile,initial=0)))\n",
    "            total += len(pile)\n",
    "        return dp(0,k,total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        pre_list = [[0] + list(itertools.accumulate(i)) for i in piles]\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if j == 0:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return pre_list[0][min(j, len(pre_list[0]) - 1)]\n",
    "            \n",
    "            Max =  0\n",
    "            for l in range(min(len(pre_list[i]), j + 1)):\n",
    "                Max =  max(Max, dp(i - 1, j - l) + pre_list[i][l])\n",
    "            return Max\n",
    "        return dp(len(piles) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if i == len(piles):\n",
    "                if k == 0: return 0\n",
    "                return -inf\n",
    "            if k == 0: return 0\n",
    "            ans = t = 0\n",
    "            for x in range(k+1):\n",
    "                if x > len(piles[i]): break\n",
    "                if x > 0: t += piles[i][x-1]\n",
    "                ans = max(ans, t+dp(i+1, k-x))\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        acc = [[] for _ in range(n)]\n",
    "        all = []\n",
    "        for i in range(n):\n",
    "            acc[i] = list(accumulate(piles[i], initial=0))[:]\n",
    "            all.append(acc[i][-1])\n",
    "        allacc = list(accumulate(all, initial=0))\n",
    "        @cache\n",
    "        def f(i, rest):\n",
    "            if rest > allacc[-1] - allacc[i]: return -inf \n",
    "            if rest == allacc[-1] - allacc[i]: return allacc[-1] - allacc[i]\n",
    "            if rest == 0: return 0\n",
    "            if i == n: return -inf\n",
    "            tmp = 0\n",
    "            for j in range(min(len(piles[i]), rest) + 1):\n",
    "                tmp = max(tmp, acc[i][j] + f(i + 1, rest - j))\n",
    "            return tmp \n",
    "        \n",
    "        return f(0, k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def process(curpos, k):\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if dp[curpos][k]:\n",
    "                return dp[curpos][k]\n",
    "            if curpos == len(piles) - 1:\n",
    "                if k > len(piles[-1]):\n",
    "                    return -sys.maxsize\n",
    "                dp[curpos][k] = sum(piles[-1][:k])\n",
    "                return dp[curpos][k]\n",
    "            base = 0\n",
    "            res = process(curpos+1, k)\n",
    "            for i in range(min(k, len(piles[curpos]))):\n",
    "                base += piles[curpos][i]\n",
    "                res = max(res, base+process(curpos+1, k-1-i))\n",
    "            dp[curpos][k] = res\n",
    "            return dp[curpos][k]\n",
    "\n",
    "\n",
    "        dp = [[0] * (k+1) for _ in range(len(piles)+1)]\n",
    "        return process(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        dp = [[0 for _ in range(k+1)] for _ in range(len(piles))]\n",
    "        for i,  pile in enumerate(piles):\n",
    "            for j in range(1, k+1):\n",
    "                dp[i][j] = dp[i][j-1] + pile[j-1] if j-1 < len(pile) else 0\n",
    "                \n",
    "        @cache\n",
    "        def xunzhao(i, nums):\n",
    "            if i == len(piles):\n",
    "                return 0\n",
    "            ret = 0\n",
    "            for j in range(min(nums, len(piles[i]))+1):\n",
    "                ret = max(ret, xunzhao(i+1, nums-j) + dp[i][j])\n",
    "            return ret\n",
    "        \n",
    "        return xunzhao(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        # @cache\n",
    "        # def dfs(i: int, j: int, c: int) -> int:\n",
    "        #     if i == -1:\n",
    "        #         return 0\n",
    "        #     if j == 0:\n",
    "        #         return 0\n",
    "        #     if c == len(piles[i]):\n",
    "        #         return dfs(i - 1, j, 0)\n",
    "        #     return max(dfs(i - 1, j, 0), dfs(i, j - 1, c + 1) + piles[i][c])\n",
    "        \n",
    "        n = len(piles)\n",
    "        cnt = max(len(piles[i]) for i in range(n))\n",
    "        dp = [[0] * (cnt + 1) for _ in range(k + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(k):\n",
    "                for c in range(len(piles[i]), -1, -1):\n",
    "                    if c == len(piles[i]):\n",
    "                        dp[j + 1][c] = dp[j + 1][0]\n",
    "                    else:\n",
    "                        if dp[j + 1][0] > dp[j][c + 1] + piles[i][c]:\n",
    "                            dp[j + 1][c] = dp[j + 1][0]\n",
    "                        else:\n",
    "                            dp[j + 1][c] = dp[j][c + 1] + piles[i][c]\n",
    "        return dp[k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        L = len(piles)\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, sur):\n",
    "            if sur == 0: return 0\n",
    "            if idx == L: return -inf\n",
    "            sum_ = 0\n",
    "            ans = dfs(idx + 1, sur)\n",
    "            for i, n in enumerate(piles[idx], start = 1):\n",
    "                sum_ += n\n",
    "                ans = max(ans, sum_ + dfs(idx + 1, sur - i))\n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(0, k)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \n",
    "        @functools.lru_cache(maxsize=2 * 10**6 + 10)\n",
    "        def dp(pile_num, remaining_coins):\n",
    "            \n",
    "            if remaining_coins == 0:\n",
    "                return 0\n",
    "            if pile_num == len(piles):\n",
    "                return 0\n",
    "\n",
    "            maxres = dp(pile_num+1, remaining_coins)\n",
    "            curval = 0\n",
    "\n",
    "            for val in piles[pile_num]:\n",
    "                if remaining_coins == 0:\n",
    "                    break\n",
    "                \n",
    "                remaining_coins -= 1\n",
    "                curval += val\n",
    "\n",
    "                res = curval + dp(pile_num+1, remaining_coins)\n",
    "                maxres = max(maxres, res)\n",
    "                    \n",
    "            return maxres\n",
    "                \n",
    "        return dp(0,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List, Any\n",
    "from functools import lru_cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param piles:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ll = []\n",
    "        for i in piles:\n",
    "            ret = []\n",
    "            cache = 0\n",
    "            for j in i:\n",
    "                cache += j\n",
    "                ret.append(cache)\n",
    "            ll.append(ret)\n",
    "        self.ll = ll\n",
    "        ret = self.get_ans(0, k)\n",
    "        return ret\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def get_ans(self, cur, restk):\n",
    "        if cur == len(self.ll) or restk == 0:\n",
    "            return 0\n",
    "        return max(self.get_ans(cur+1, restk), max([v + self.get_ans(cur + 1, restk - k - 1) if k < restk else 0 for k, v in enumerate(self.ll[cur])]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def dfs(self, i, left):\n",
    "        if left <= 0 or i == self.n:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for j in range(min(left + 1, len(self.accs[i]))):\n",
    "            res = max(res, self.dfs(i + 1, left - j) + self.accs[i][j])\n",
    "        return res\n",
    "    \n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        self.accs = [list(accumulate(pile, initial=0)) for pile in piles]\n",
    "        self.n = len(piles)\n",
    "        \n",
    "        return self.dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        for p in piles:\n",
    "            n = len(p)\n",
    "            for i in range(1, n):\n",
    "                p[i] += p[i-1]\n",
    "\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii, kk):\n",
    "            if ii < 0 or kk == 0:\n",
    "                return 0\n",
    "\n",
    "            ans = dp(ii-1, kk)\n",
    "            n = len(piles[ii])\n",
    "            for i in range(n):\n",
    "                if i+1 > kk:\n",
    "                    break\n",
    "\n",
    "                ans = max(ans, piles[ii][i] + dp(ii-1, kk - (i+1)))\n",
    "            return ans\n",
    "\n",
    "        return dp(len(piles)-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "\n",
    "        # 前缀和\n",
    "        pre = []\n",
    "        for pile in piles:\n",
    "            acc = [0]\n",
    "            for dp in pile:\n",
    "                acc.append(acc[-1] + dp)\n",
    "            pre.append(acc)\n",
    "\n",
    "        # 初始化\n",
    "        dp = defaultdict(lambda:defaultdict(int))\n",
    "        for x in range(min(k, len(piles[0])) + 1):  # 不能超过堆的长度\n",
    "            dp[0][x] = pre[0][x]\n",
    "\n",
    "        # 递推\n",
    "        for curIdx in range(1, len(piles)):\n",
    "            for y in range(k + 1):\n",
    "                for x in range(min(y, len(piles[curIdx])) + 1):  # 不能超过堆的长度\n",
    "                    dp[curIdx][y] = max(\n",
    "                        dp[curIdx][y],\n",
    "                        dp[curIdx - 1][y - x] + pre[curIdx][x])\n",
    "\n",
    "        return dp[len(piles) - 1][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        pre = []\n",
    "        for pile in piles:\n",
    "            acc = [0]\n",
    "            for m in pile:\n",
    "                acc.append(acc[-1] + m)\n",
    "            pre.append(acc)\n",
    "        \n",
    "        dp = defaultdict(lambda: defaultdict(int))\n",
    "        for x in range(min(k, len(piles[0])) + 1):\n",
    "            dp[0][x] = pre[0][x]\n",
    "        \n",
    "        for curIdx in range(1, len(piles)):\n",
    "            for y in range(k + 1):\n",
    "                for x in range(min(y, len(piles[curIdx])) + 1):\n",
    "                    dp[curIdx][y] = max(dp[curIdx][y], dp[curIdx - 1][y - x] + pre[curIdx][x])\n",
    "        \n",
    "        return dp[len(piles) - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        @cache\n",
    "        def dfs(i=0,cnt=k):\n",
    "            if cnt == 0:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return -inf\n",
    "            ans = dfs(i+1,cnt)\n",
    "            val = 0\n",
    "            for j in piles[i]:\n",
    "                val +=j\n",
    "                cnt -= 1\n",
    "                if cnt <0:\n",
    "                    break\n",
    "                ans = max(ans,val+dfs(i+1,cnt))\n",
    "            return ans\n",
    "        return dfs(0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        pre_sum = [list(accumulate(x,initial = 0)) for x in piles]\n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if i < 0:\n",
    "                return -inf\n",
    "            ans = 0\n",
    "            for j in range(min(k + 1,len(piles[i]) + 1)):\n",
    "                ans = max(ans,pre_sum[i][j] + dfs(i - 1,k - j))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(n - 1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "       n = len(piles)\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n or j == k:\n",
    "             return 0\n",
    "          res = dfs(i + 1, j)\n",
    "          sum = 0\n",
    "          cnt = 0\n",
    "          for x in piles[i]:\n",
    "             sum += x\n",
    "             cnt += 1\n",
    "             if j + cnt > k:\n",
    "                break\n",
    "             res = max(res, dfs(i + 1, j + cnt) + sum)\n",
    "          return res\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        pre = [list(itertools.accumulate(p, initial=0)) for p in piles]\n",
    "        l = [len(p) for p in piles]\n",
    "        @cache\n",
    "        def f(i, x):\n",
    "            if x < 0:\n",
    "                return -math.inf\n",
    "            if i == 0:\n",
    "                return -math.inf if x > l[i] else pre[i][x]\n",
    "            ans = -math.inf\n",
    "            for j in range(min(x,l[i])+1):\n",
    "                ans = max(ans, f(i-1, x-j) + pre[i][j])\n",
    "            return ans\n",
    "\n",
    "        return f(n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        pre = [[0] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(len(piles[i])):             \n",
    "                pre[i].append(pre[i][-1] + piles[i][j])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, k):\n",
    "            if i == n:\n",
    "                if k == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return -inf\n",
    "            \n",
    "            maxl = 0\n",
    "            for j in range(min(len(piles[i]), k) + 1):\n",
    "                maxl = max(maxl, dfs(i + 1, k - j) + pre[i][j])\n",
    "            return maxl\n",
    "        \n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        n=len(piles)\n",
    "        xx=[[-1 for _ in range(k+1)] for __ in range(n)]\n",
    "        for i in range(n):\n",
    "            xx[i][0]=0\n",
    "        @cache\n",
    "        def dwjs(p,k)->int:\n",
    "            r=0\n",
    "            i=0\n",
    "            if p==0:\n",
    "                x=min(len(piles[0]),k)\n",
    "                for i in range(x):\n",
    "                    r+=piles[0][i]\n",
    "                    xx[0][i+1]=r\n",
    "                \n",
    "                while i<k:\n",
    "                    xx[0][i+1]=r\n",
    "                    i+=1\n",
    "                return r\n",
    "\n",
    "            i=0\n",
    "            r=0\n",
    "            ret=dwjs(p-1,k)\n",
    "            #print('R',ret,p)\n",
    "            while i<k and i<len(piles[p]):\n",
    "                r+=piles[p][i]\n",
    "                #w=r+xx[p-1][k-i-1]\n",
    "                w=r+dwjs(p-1,k-i-1)\n",
    "                if ret<w:\n",
    "                    ret=w\n",
    "                i+=1\n",
    "            xx[p][k]=ret\n",
    "            return ret\n",
    "            \n",
    "\n",
    "\n",
    "        ret=dwjs(n-1,k)\n",
    "        #print(xx)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "from typing import List\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 1 <= k <= sum(piles[i].length) <= 2000\n",
    "# 1 <= n <= 1000\n",
    "\n",
    "# 这道题时间复杂度为O(k*sum(piles[i].length))\n",
    "# https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \"\"\"时间复杂度O(背包容量*物品个数)\"\"\"\n",
    "\n",
    "        def max(a: int, b: int) -> int:\n",
    "            return a if a > b else b\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, remain: int) -> int:\n",
    "            if index == n:\n",
    "                return 0 if remain == 0 else -INF\n",
    "\n",
    "            res = 0\n",
    "            curGroup, curSum = piles[index], 0\n",
    "            res = dfs(index + 1, remain)\n",
    "            for select in range(1, min(remain, len(curGroup)) + 1):\n",
    "                curSum += curGroup[select - 1]\n",
    "                res = max(res, dfs(index + 1, remain - select) + curSum)\n",
    "            return res\n",
    "\n",
    "        n = len(piles)\n",
    "        res = dfs(0, k)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \n",
    "        n = len(piles)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, pre):\n",
    "            if i == n:\n",
    "                return 0 if pre == 0 else -inf\n",
    "            res = dfs(i+1, pre)\n",
    "            m = len(piles[i])\n",
    "            cur = 0\n",
    "            for x in range(m):\n",
    "                cur += piles[i][x]\n",
    "                if x+1>pre:\n",
    "                    break\n",
    "                nex= cur + dfs(i+1, pre-x-1)\n",
    "                if nex > res:\n",
    "                    res = nex\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        mem = {}\n",
    "        def dfs(piles, index, k):\n",
    "            if index == len(piles):\n",
    "                return 0\n",
    "            if (index,k) in mem:\n",
    "                return mem[(index, k)]\n",
    "\n",
    "            cur = piles[index]\n",
    "            res = 0\n",
    "            cur_sum = 0\n",
    "            for i in range(min(len(cur),k)):\n",
    "                cur_sum += cur[i]\n",
    "                res = max(res, cur_sum + dfs(piles, index+1, k-i-1))\n",
    "            res = max(res, dfs(piles, index+1, k))\n",
    "            mem[(index,k)] = res\n",
    "            return res\n",
    "\n",
    "        ans = dfs(piles, 0, k)\n",
    "        # print(mem)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        @cache\n",
    "        def dp(i,k):\n",
    "            if k==0 or i==-1:\n",
    "                return 0\n",
    "            res=dp(i-1,k)\n",
    "            cur=0\n",
    "            for j in range(min(len(piles[i]),k)):\n",
    "                cur+=piles[i][j]\n",
    "                res=max(res, cur+dp(i-1,k-j-1))\n",
    "            return res\n",
    "        return dp(len(piles)-1, k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        from functools import cache\n",
    "        @cache\n",
    "        def dfs(i, k):\n",
    "            if k == 0 or i == -1:\n",
    "                return 0\n",
    "            ans, cursum = 0, 0\n",
    "            for j in range(min(len(piles[i]), k) + 1):\n",
    "                ans = max(ans, cursum + dfs(i - 1, k - j))\n",
    "                if j < len(piles[i]):\n",
    "                    cursum += piles[i][j]\n",
    "            return ans\n",
    "        return dfs(len(piles) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n",
    "        \"\"\"\n",
    "        n = len(piles)\n",
    "        pre_sum = []\n",
    "\n",
    "        for pile in piles:\n",
    "            m = len(pile)\n",
    "            _pre_sum = [0] * (m + 1)\n",
    "            for i in range(m):\n",
    "                _pre_sum[i + 1] = _pre_sum[i] + pile[i]\n",
    "            \n",
    "            pre_sum.append(_pre_sum)\n",
    "\n",
    "        超时了\n",
    "        @cache\n",
    "        def dfs(i, cur_k, total_ops):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "\n",
    "            ret = pre_sum[i][cur_k]\n",
    "            left_ops = k - total_ops\n",
    "            if i < n - 1:\n",
    "                left_ops = min(left_ops, len(piles[i + 1]))\n",
    "\n",
    "            ret += max(dfs(i + 1, j, total_ops + j) for j in range(left_ops + 1))\n",
    "            \n",
    "            return ret\n",
    "\n",
    "        \n",
    "        return max(dfs(0, j, j) for j in range(min(k + 1, len(piles[0]) + 1)))\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        可以看做背包问题，每个栈是1个物品，栈的前缀和是物品的价值，其所需要的体积是栈的前缀长度（操作数）\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        dp = [[0]*(k + 1) for _ in range(len(piles))]\n",
    "        for v in range(1, min(len(piles[0]), k) + 1):\n",
    "            dp[0][v] = dp[0][v - 1] + piles[0][v - 1]\n",
    "\n",
    "        for i in range(1, len(piles)):\n",
    "            pile = piles[i]\n",
    "            n = len(pile)\n",
    "\n",
    "            # 前缀和\n",
    "            for j in range(1, n):\n",
    "                pile[j] += pile[j - 1]\n",
    "            \n",
    "            # 遍历操作数\n",
    "            for v in range(1, k + 1):\n",
    "                # dp[i - 1][v]是用i-1个栈，操作数为v的价值\n",
    "                # 对于pile，可操作的次数为min(n, v)，然后遍历所有可能得操作数，取最大值\n",
    "                dp[i][v] = max(dp[i - 1][v], max(dp[i - 1][v - w - 1] + pile[w] for w in range(min(n, v))))\n",
    "        \n",
    "        return dp[-1][k]\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(piles)\n",
    "        for pile in piles:\n",
    "            for i in range(1, len(pile)):\n",
    "                pile[i] += pile[i - 1]\n",
    "        @cache\n",
    "        def dp(i, kk):\n",
    "            \"\"\"\n",
    "            到了第i个栈，还可以操作kk次\n",
    "            \"\"\"\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            if kk <= 0:\n",
    "                return 0\n",
    "\n",
    "            ret = dp(i + 1, kk)\n",
    "            for j in range(min(kk, len(piles[i]))):\n",
    "                ret = max(ret, dp(i + 1, kk - j - 1) + piles[i][j])\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        return dp(0, k)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
